// https://leetcode.cn/problems/set-matrix-zeroes/
#include <vector>
#include <set>
#include <iostream>

using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
		set<int> rows;
		set<int> cols;
		
		int row = matrix.size();
		int col = matrix[0].size();
		for(int i = 0; i < row; i++){
			for(int j = 0; j < col; j++){
				if(matrix[i][j] == 0){
					rows.insert(i);
					cols.insert(j);
				}
			}
		}
		for(int i = 0; i < row; i++){
			if(rows.find(i) != rows.end()){
				for(int j = 0; j < col; j++){
					matrix[i][j] = 0;
				}
			}
		}
		for(int i = 0; i < col; i++){
			if(cols.find(i) != cols.end()){
				for(int j = 0; j < row; j++){
					matrix[j][i] = 0;
				}
			}
		}
		
    }
	
	void show(vector<vector<int>>& matrix){
		int row = matrix.size();
		int col = matrix[0].size();
		for(int i = 0; i < row; i++){
			for(int j = 0; j < col; j++){
				cout << matrix[i][j] << ",";
			}
			cout << endl;
		}
	}
};

int main(){
	Solution so;
	vector<vector<int>> m = {{1,1,1},{1,0,1},{1,1,1}};
	so.setZeroes(m);
	so.show(m);
	return 0;
}